Description
Switches and routers used in packet networks, such as the Internet, are store-and-forward devices. In these types of devices, the arriving packets are initially stored in memory. The packets are later read out and forwarded to the appropriate destination. A scheduling algorithm determines when to forward a packet out of the switch or router. The data in memory can be organized as several queues, based on the attributes of the incoming data, such as its destination, class of service, etc. The number of queues used in packet switches and routers has been increasing dramatically due to both an increase in total throughput, and the use of fine-grained Quality of Service (QoS) among a large number of traffic streams.
A search for the next available queue can be performed serially. In this case, one queue at a time is checked for occupancy (one or more clock cycles per queue). As the number of queues to be searched increases, the time to do the search also increases. For example, if it takes k cycles to check for occupancy of each queue, then the time to search through N queues in k×N clock cycles. For instance, if N is a million queues and k is 2 cycles, then it would take 2 million cycles to find the next queue in the worst case.
A search for the next available queue can be performed in parallel. A parallel circuit can be designed which accepts the entire state of the queues as its inputs. Such a circuit would have as its inputs, hundreds of thousands, or even millions, of signals corresponding to the occupancy status of the queues and a corresponding number of gates to determine the next non-zero queue. The cumulative gate delays through this logic may be considerable.
Moreover, some of the queues may be temporarily ineligible for service for any number of reasons including, but not limited to (a) the switch or router may employ a selective backpressure mechanism to flow-control specific queues, (b) the scheduling algorithm may exclude specific queues temporarily because they have met or exceeded performance targets; and (c) the switch may temporarily suspend service to queues that are in violation of performance criteria.
Furthermore, the state of one or more of the queues, empty or non-empty, may change during the process of searching through the queues. This is because the data coming into the queues is asynchronous with data being sent out of the queues. The eligibility status of individual queues may also change during the search.